package cn.edu.xjtu.competiton.力扣.双周赛.biweekly77;

/**
 * @author Hydrion-QLz
 * @date 2022-04-30 23:14
 * @description https://leetcode-cn.com/contest/biweekly-contest-77/problems/minimum-average-difference/
 */
public class Second {
    public static void main(String[] args) {
        Second solution = new Second();
        int[] arr = {2, 5, 3, 9, 5, 3};
        System.out.println(solution.minimumAverageDifference(arr));
    }

    public int minimumAverageDifference(int[] nums) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i] = sum;
            sum += nums[i];
        }

        prefixSum[n] = sum;
        int idx = 0;
        long min_val = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long preAvg = prefixSum[i + 1] / (i + 1);
            long sufAvg = (prefixSum[n] - prefixSum[i + 1]) / ((n - i - 1) == 0 ? 1 : (n - i - 1));
            long sub = Math.abs(preAvg - sufAvg);
            if (sub < min_val) {
                min_val = sub;
                idx = i;
            }
        }
        return idx;
    }
}
